The present invention relates to an error correction system for automatically correcting the errors in a digital transmission system and/or a digital memory, and in particular, relates to such a system which corrects the simultaneous two or three errors.
A prior error correction system transmits a series of information bits together with some test bits, and a transmission error is automatically corrected in a reception side according to the test bits. A BCH (Bose, Chaudhuri, Hocquenghem code) is one of the error correction codes with some test bits. Said BCH code can adapt to a variety of code lengths, and has an excellent error correction capability in a given number of test bits. Among the BCH codes, a single error correction code, a two error correction code, and a three error correction code are typical. The present invention relates to an error correction system which corrects two or three errors in each word.
First, a two-error correction system is described.
One of the prior arts calculates the value A.sub.2 /A.sub.1 +A.sub.2.sup.2 from the first and the second syndromes A.sub.1 and A.sub.2 which will be described later, and using said value, the error position polynominal; EQU .sigma.(Z)=1+A.sub.1 Z+(A.sub.2 /A.sub.1 +A.sub.1.sup.2)Z.sup.2
is produced. Then, .alpha..sup.-t (t=1, 2, . . . , and .alpha. is a primitive element of a Galois field) is substituted to the value Z in the above equation, and the position that the value of said equation is zero, is the position of the error. However, said prior art has the disadvantage that a large amount of the calculation process is necessary to calculate the division A.sub.2 /A.sub.1.
Another prior art is the ROM (Read-Only-Memory) table method, in which a syndrome is produced in a feedback shift register which corresponds to a generation polynominal by inputting a reception code in said register, and consulting with a ROM table which shows the relations with the pattern of a syndrome and an error position. This method has the advantage that the error correction is performed with a simple structure. However, it has the disadvantage that the capacity or the number of words of a ROM table is too large when the degree of the generation polynominal is high, since that ROM table is consulted with the address having the same number of bits as the degree of the generation polynominal. At present, when the degree of the generation polynominal is higher than 16, the ROM table is not obtained with a reasonable size.
In a three error correction system, a first syndrome A.sub.1, a second syndrome A.sub.2 and a third syndrome A.sub.3 are calculated. The calculation of those syndromes is described later. Then, the error position polynominal .sigma.(Z) is calculated as follows. ##EQU3## Then, .alpha..sup.t (t=1, 2, . . . , n) is substituted in said .sigma.(Z), and determines that the value t which provides .sigma.(Z)=0 indicates the errored position. The correction is performed by inverting the data at the position t.
However, that prior system has the disadvantage that a complicated divider must be utilized for calculating the above equations.